package class05;

import java.util.HashSet;

/**
 * 位图: 一个int数字需要占 4字节.
 * 假如使用一个int的数字的bit位来判断一个数是否存在, 有32位, 则最大能表示 32 个数是否出现过.
 * (只存32个数字局限性比较大,虽然节省了31*4字节的空间).
 * 那么如何表示更多的数是否出现过?
 * 使用一个数组: int[32], 长度为32,每个下标存一个int, 那么就能判断 32 * 32 = 1024个数.
 * 数组0位置表示 0 ~ 31 是否出现, 数组1位置表示 32 ~ 63 是否出现过 ...
 * 节约了 (1024-32)*4 字节空间.
 *
 * 位图的功能: 确定数字的上限情况下, 判断数据是否存在, 节约存储空间.
 */
public class Code02_BitMap2 {

  // 这个类的实现是正确的
  public static class BitMap {

    private long[] bits;

    public BitMap(int max) {
    	//(max + 64) >> 6 (max + 64) >> 6  等价于  (max + 64) / 64
		//根据最大值判断需要几个数放到数组中
      bits = new long[(max + 64) >> 6];
    }

    public void add(int num) {
    	// 思路:
		// 1.找到需要在哪个下标对应的值标记数字存在
		// 2.判断要存的数字在二进制的第几位
		// 3.对该位的比特位置1
    	// num >> 6 判断需添加的数字在第几个整数(下标): 5为例子, 5>>6 = 0
		// num % 64 就能表示当前数是在所在下标的数字(int[x])的第几位: 5%64=5
		// 取模(%)运算效率偏低, 可以直接使用 num & 63 取代(num % 64): 5&63=5
		// 1L << (num & 63) 表示该数在当前下标值的第几个比特位: 省略前面的零 0001 0000
      bits[num >> 6] |= (1L << (num & 63));
    }

    public void delete(int num) {
    	//将数字对应位置的标识改为 0
		// ~(1L << (num & 63)) 表示该数在当前下标值的第几个比特位取反置为0: 省略前面的零 1110 1111
      bits[num >> 6] &= ~(1L << (num & 63));
    }

    public boolean contains(int num) {
      return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }
  }

  public static void main(String[] args) {
    System.out.println("测试开始！");
    int max = 10000;
    BitMap bitMap = new BitMap(max);
    HashSet<Integer> set = new HashSet<>();
    int testTime = 10000000;
    for (int i = 0; i < testTime; i++) {
      int num = (int) (Math.random() * (max + 1));
      double decide = Math.random();
      if (decide < 0.333) {
      	// 1/3 的概率增加一个数
        bitMap.add(num);
        set.add(num);
      } else if (decide < 0.666) {
      	// 2/3 的概率删一个数
        bitMap.delete(num);
        set.remove(num);
      } else {
        if (bitMap.contains(num) != set.contains(num)) {
          System.out.println("Oops!");
          break;
        }
      }
    }
    for (int num = 0; num <= max; num++) {
      if (bitMap.contains(num) != set.contains(num)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("测试结束！");
  }
}
